/**
 * 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
 *
 * 链接：https://leetcode.cn/problems/get-kth-magic-number-lcci
 *
 */
class GetKthMagicNumber {
    /**
     * 法一：最小堆
     * @param k
     * @return
     */
    public int getKthMagicNumberPriority(int k) {
    int[] factors={3,5,7};
    Set<Long> seen=new HashSet<>();
    PriorityQueue<Long> heap=new PriorityQueue<>();
    seen.add(1L);
    heap.offer(1L);
    int magic=0;
    for(int i=0;i<k;i++) {
        long cur=heap.poll();
        magic=(int)cur;
        for(int factor:factors) {
            long next=cur*factor;
            if(seen.add(next)) {
                heap.offer(next);
            }
        }
    }
    return magic;
    }

    /**
     * 法二：三指针
     * @param k
     * @return
     */
    public int getKthMagicNumberThreeOfPoint(int k) {
        int[] numList=new int[k+1];
        int p3=0;
        int p5=0;
        int p7=0;
        numList[0]=1;
        for(int i=1;i<k;i++) {
            numList[i]=Math.min(Math.min(numList[p3]*3,numList[p5]*5),numList[p7]*7);
            if(numList[i]==numList[p3]*3) {
                p3++;
            }
            if(numList[i]==numList[p5]*5) {
                p5++;
            }
            if(numList[i]==numList[p7]*7) {
                p7++;
            }
        }
        return numList[k-1];
    }
}